/*
 * Created on 20.04.2006
 * 
 * To change the template for this generated file go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
package robocup.component.math;

public class PermutationEvaluator {

  /**
   * recursive method that finds a minimal sum for a permutation of values
   * 
   * @param matrix -
   *          the base-matrix containing the corresponding values
   * @param rowIdx -
   *          the row index (starting with 0)
   * @param wayTaken -
   *          the way in the matrix that was used to reach the current point
   * @param bestWay -
   *          the way that lead to the smallest sum
   * @param sums -
   *          sum[0] the current sum, sum[1] the best sum found so far
   * @param columnUsed -
   *          all columns that wer already used are set to false
   */
  public static void smallestPermutation(final double[][] matrix,
      final int rowIdx,
      final int[] wayTaken,
      final int[] bestWay,
      final double[] sums,
      final boolean[] columnUsed) {

    // reached a leaf -> recursion ends here
    if (rowIdx == matrix.length) {
      if (sums[0] < sums[1]) {
        sums[1] = sums[0];
        System.arraycopy(wayTaken, 0, bestWay, 0, bestWay.length);
      }

      return;
    }

    final double currentSum = sums[0];

    // go ahead for all nodes
    for (int j = 0; j < matrix[rowIdx].length; j++) {
      if (matrix[rowIdx][j] >= 0) {
        if (columnUsed[j]) {
          continue;
        }

        final double newSum = currentSum + matrix[rowIdx][j];

        // as some ways in the tree are obviously bad skip them
        if (newSum > sums[1]) {
          continue;
        }
        else {
          columnUsed[j] = true;
          wayTaken[rowIdx] = j;
          sums[0] = newSum;

          // do it again
          PermutationEvaluator.smallestPermutation(matrix, rowIdx + 1,
              wayTaken, bestWay, sums, columnUsed);
          columnUsed[j] = false;
        }
      }
      else {
        continue;
      }
    }
  }

}
